-module(sort).
-export([quicksort/1]).

%% quicksort(A)
%%	Inputs:
%%		A = unsorted List
%%	Returns
%%		sorted List
quicksort(A)->
	quicksort(A, []).	

quicksort([Key|Rest], Tail)->
	{Smaller, Bigger} = split(Key, Rest),
	quicksort(Smaller, [Key | quicksort(Bigger, Tail)]);
quicksort([], Tail)->
	Tail.


split(Key, L)->
	split(Key, L, [], []).

split(_, [], Smaller, Bigger)->
	{Smaller, Bigger};
split(Key, [H|T], Smaller, Bigger) when H < Key ->
	split(Key, T, [H|Smaller], Bigger);
split(Key, [H|T], Smaller, Bigger) when H >= Key ->
	split(Key, T, Smaller, [H | Bigger]).
